#ifndef STX_ALGORITHM_MINMAX_ELEMENT_HPP
#define STX_ALGORITHM_MINMAX_ELEMENT_HPP

#include <stx/algorithm/common.hpp>

namespace stx {

template <class ForwardIterator, class Compare>
inline std::pair<ForwardIterator, ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last, Compare comp)
{
    std::pair<ForwardIterator, ForwardIterator> result(first, first);
    if (first != last) {
        if (++first != last) {
            if (comp(*first, *result.first)) {
                result.second = result.first;
                result.first = first;
            } else {
                result.second = first;
            }
            while (++first != last) {
                ForwardIterator i = first;
                if (++first == last) {
                    if (comp(*i, *result.first)) {
                        result.first = i;
                    } else if (!comp(*i, *result.second)) {
                        result.second = i;
                    }
                    break;
                } else {
                    if (comp(*first, *i)) {
                        if (comp(*first, *result.first)) {
                            result.first = first;
                        }
                        if (!comp(*i, *result.second)) {
                            result.second = i;
                        }
                    } else {
                        if (comp(*i, *result.first)) {
                            result.first = i;
                        }
                        if (!comp(*first, *result.second)) {
                            result.second = first;
                        }
                    }
                }
            }
        }
    }
    return result;
}

template <class ForwardIterator>
inline std::pair<ForwardIterator, ForwardIterator>
minmax_element(ForwardIterator first, ForwardIterator last)
{
    return stx::minmax_element(
        first,
        last,
        stx::less<typename std::iterator_traits<ForwardIterator>::value_type>());
}

} // namespace stx

#endif // STX_ALGORITHM_MINMAX_ELEMENT_HPP
